package offer.offer01;

/**
 * 100, 100, 前序遍历整个A树, 当找到与B树根节点相同的节点时, 调用另一个函数判断这个节点的A的子树是否包含B树中的每一个节点, 且位置相同。主要需要排除空指针。
 */
public class S26树的子结构 {

    public boolean isSubStructure(TreeNode A, TreeNode B) {
        if(A == null || B == null) return false;
        if(A.val == B.val){
            //当A的根与B的根相同时, 查看B是不是在A里面
            if(isBInA(A, B)) {
                return true;
            }else {
                if(isSubStructure(A.left, B) || isSubStructure(A.right, B)){
                    return true;
                }
            }
        }else {
            if(isSubStructure(A.left, B) || isSubStructure(A.right, B)){
                return true;
            }
        }
        return false;
    }

    public boolean isBInA(TreeNode subA, TreeNode B){
        if(B == null) return true;
        //B不为空的情况下, subA为一个空树, 返回false
        if(subA == null) return false;
        if(B.val == subA.val){
            return isBInA(subA.left, B.left) && isBInA(subA.right, B.right);
        }else {
            return false;
        }
    }

    // 猛男落泪。
    public boolean isSubStructure2(TreeNode A, TreeNode B) {
        return (A != null && B != null) && (recur(A, B) || isSubStructure(A.left, B) || isSubStructure(A.right, B));
    }
    boolean recur(TreeNode A, TreeNode B) {
        if(B == null) return true;
        if(A == null || A.val != B.val) return false;
        return recur(A.left, B.left) && recur(A.right, B.right);
    }

}
class TreeNode {
    int val;
    offer.offer01.TreeNode left;
    offer.offer01.TreeNode right;
    TreeNode(int x) { val = x; }
}
